Zápočet 27.1.2010

Popiste TS pre jazyk $L={aibici;i∈N}L=\{a^{i}b^{i}c^{i}; i \in N\}$
Ukazke ze $s i g n (x)$ je PRF
Za pomoci nektereho problemu z prednasky dokazte, ze Hamiltonovska cesta $H C (s, t)$ je NP-uplny problem
Ukazte, ze pre hornovsku KNF existuje polynomialny algoritmus, ktory najde splnujuce ohodnotenie